//
// Created by Admin on 2021/9/23.
//

#include "binarySearchTree.h"

pBinarySearchTree makeTree(){
    return calloc(1,sizeof(BinarySearchTree));
}

void destroyTreeNodes(pTreeNode treeNode){
    if(treeNode==NULL) return;
    if(treeNode->l_child){
        destroyTreeNodes(treeNode->l_child);
    }
    if(treeNode->r_child){
        destroyTreeNodes(treeNode->r_child);
    }
    free(treeNode);
}

void destroyTree(pBinarySearchTree binarySearchTree){
    pTreeNode node = binarySearchTree->root;
    if(node!=NULL){
        destroyTreeNodes(node);
    }
    free(binarySearchTree);
}

void insertNode_int(pBinarySearchTree binarySearchTree,int data){
    pTreeNode parent = binarySearchTree->root;
    if(binarySearchTree->root == NULL){
        binarySearchTree->root = calloc(1, sizeof(TreeNode));
        binarySearchTree->root->data = data;
        return;
    }
    while(1){
        if(data == parent->data) return;
        if(data > parent->data){
            if(parent->r_child==NULL){
                parent->r_child = calloc(1,sizeof(TreeNode));
                parent->r_child->parent = parent;
                parent->r_child->data = data;
                return;
            }else{
                parent = parent->r_child;
            }
        } else{
            if(parent->l_child==NULL){
                parent->l_child = calloc(1,sizeof(TreeNode));
                parent->l_child->parent = parent;
                parent->l_child->data = data;
                return;
            }else{
                parent = parent->l_child;
            }
        }
    }
}

void inOrderVisit(pTreeNode treeNode){
    if(treeNode==NULL) return;
    inOrderVisit(treeNode->l_child);
    printf(" -> %d",treeNode->data);
    inOrderVisit(treeNode->r_child);
}

void inOrderVisitTree(pBinarySearchTree binarySearchTree){
    pTreeNode node = binarySearchTree->root;
//    if(node==NULL) return;
    inOrderVisit(node);
    printf("\n");
}

pTreeNode searchNode(pBinarySearchTree binarySearchTree,int data){
    pTreeNode node = binarySearchTree->root;
    if(node==NULL) return NULL;
    while(1){
        if(data==node->data) return node;
        if(data>node->data){
            if(node->r_child==NULL) return NULL;
            node = node->r_child;
        }else{
            if(node->l_child==NULL) return NULL;
            node = node->l_child;
        }
    }
}

void removeNode(pBinarySearchTree binarySearchTree, int data, pTreeNode treeNode){
    pTreeNode node = treeNode==NULL?searchNode(binarySearchTree,data):treeNode;
    if(node==NULL) return;
    pTreeNode parent = node->parent;
    int isNodeLeft = parent->l_child == node;
    //如果是叶子节点，修正指针后可以直接删除
    if(node->l_child==NULL && node->r_child==NULL){
        if(isNodeLeft){
            parent->l_child = NULL;
        } else{
            parent->r_child = NULL;
        }
        free(node);
        return;
    }
    //左子树非空，右子树为空，用左子树取代当前节点
    if(node->l_child!=NULL && node->r_child==NULL){
        pTreeNode child = node->l_child;
        if(isNodeLeft){
            parent->l_child = child;
        }else{
            parent->r_child = child;
        }
        free(node);
        return;
    }
    //右子树非空，左子树为空，用右子树取代当前节点
    if(node->l_child==NULL && node->r_child!=NULL){
        pTreeNode child = node->r_child;
        if(isNodeLeft){
            parent->l_child = child;
        }else{
            parent->r_child = child;
        }
        free(node);
        return;
    }
    //左右子树非空，可以
    //1.从左子树中挑一个最大的节点挂上去，或
    //2.从右子树中挑一个最小的节点挂上去
    //然后递归删除被挑中的节点
    if(node->l_child!=NULL&&node->r_child!=NULL){
        pTreeNode child = node->l_child;
        while(child->r_child!=NULL){
            child = child->r_child;
        }
        node->data = child->data;
        removeNode(binarySearchTree, -1, child);
    }
}